男人八题 做题记录

Jump!

$1/8$：$AStringGame$

签到题？加字符就是在 SAM 上跑，算出 SAM 的 SG 函数即可。

$Code$

$2/8$：$SignLocation$

结论是最优方案一定放在整点上！！伪证明考虑微扰：假设两个相邻车站的距离为 $dis$，左右点数各为 $l$ 和 $r$，当前是 $dis l$，那么移到中间后是 $dis \frac{n}{2}$，因为 $l \leq \frac{n}{2}$ 所以不会变优。

$f_{i, j}$ 表示当前放了 $i$ 个，最后一个在 $j$ 位置。决策点感性理解下是单调不减的？并且据说也是凸的。我用的是决策单调性，贡献用前缀和什么的就能计算，随便做。数据有点水

$Code$

$3/8$：$PerfectNPArray$

很明显这个「全部 $\geq 0$」是在演你—— $< 0$ 截掉无影响。

冷静分析一波，由于可以反走下降路径，经过一个点最大的路径前缀是经过它的路径的 $\min( |mx|, |mn| )$。记录每棵子树的最大最小次大次小链。

$Code$

$4/8$：$EquationsAndInequations$

未完……

先按照偏序关系和相等关系算出划分方案，再算依照这种划分方案的大小关系来，$\sum x_i = s$ 的解数。假设大小关系已经完全确定。可是直接算很难遵守大小关系，考虑差分。将 $x$ 差分，设 $\sum\limits_{j = i}^m = a_i$, 应满足 $\sum a_i x_i = s$，即 $[x^s] \prod\limits_{i = 1}^m \frac{x^{a_i}}{1 - x^{a_i}}$

后面不会了

$5/8$：$IntervalTree$

神……

$6/8$：